package com.lhcai.nk;

/**
 * @author lhcstart
 * @create 2023-02-23 17:38
 */

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;


/**
 * 描述
 * 给出一组区间，请合并所有重叠的区间。
 * 请保证合并后的区间按区间起点升序排列。
 * <p>
 * 数据范围：区间组数 0≤n≤2×10^5，区间内 的值都满足0≤val≤2×10^5
 * <p>
 * 要求：空间复杂度 O(n)，时间复杂度 O(nlogn)
 * 进阶：空间复杂度O(val)，时间复杂度O(val)
 */
public class NC37 {
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {

        ArrayList<Interval> res = new ArrayList<>();
        if (intervals.size() == 0) {
            return res;
        }

        Collections.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                if (o1.start != o2.start) {
                    return o1.start - o2.start;
                } else {
                    return o1.end - o2.end;
                }
            }
        });

        res.add(intervals.get(0));
        //用来计算res 中的元素
        int count = 0;
        //遍历后续区间，查看是否与末尾有重叠
        for (int i = 1; i < intervals.size(); i++) {
            Interval o1 = intervals.get(i);
            Interval origin = res.get(count);
            //没有重叠
            if (o1.start > origin.end) {
                res.add(o1);
                count++;
            } else {
                res.remove(count);
                Interval s = new Interval(origin.start, o1.end);
                if (o1.end < origin.end) {
                    s.end = origin.end;
                }
                res.add(s);
            }
        }
        return res;
    }

    public class Interval {
        int start;
        int end;

        Interval() {
            start = 0;
            end = 0;
        }

        Interval(int s, int e) {
            start = s;
            end = e;
        }
    }
}
